package cn.xdf.learn.leetcode.动态规划;


import java.util.HashMap;
import java.util.Map;

/**
 *   * 作者：捡田螺的小男孩
 *      * 链接：https://juejin.cn/post/6951922898638471181
 *      * 来源：稀土掘金
 *      * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 *
 */
public class Jump {

    public static void main(String[] args) {

        int r = numWays3(5);
        System.out.println(r);

    }


    /**
     * 暴力递归
     * @param n
     * @return
     */
    public static int numWays1(int n) {
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        return numWays1(n-1) + numWays1(n-2);
    }


    /**
     * 带备忘录的递归方法
     */
    //使用哈希map，充当备忘录的作用
    Map<Integer, Integer> tempMap = new HashMap();
    public int numWays2(int n) {
        // n = 0 也算1种
        if (n == 0) {
            return 1;
        }
        if (n <= 2) {
            return n;
        }
        //先判断有没计算过，即看看备忘录有没有
        if (tempMap.containsKey(n)) {
            //备忘录有，即计算过，直接返回
            return tempMap.get(n);
        } else {
            // 备忘录没有，即没有计算过，执行递归计算,并且把结果保存到备忘录map中，对1000000007取余（这个是leetcode题目规定的）
            tempMap.put(n, (numWays2(n - 1) + numWays2(n - 2)) % 1000000007);
            return tempMap.get(n);
        }
    }



    /**

     * <p>
     * <p>
     * 动态规划
     *
     * @param n
     * @return
     */
    public static int numWays3(int n) {
        if (n <= 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int a = 1;
        int b = 2;
        int temp = 0;
        for (int i = 3; i <= n; i++) {
            temp = (a + b);
            temp = temp % 1000000007;
            a = b;
            b = temp;
        }
        return temp;
    }


}
